/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
  // 深度优先遍历
    TreeNode* addOneRow(TreeNode* root, int val, int depth) {
        if(root == nullptr) return root;
        if(1 == depth)  //创建一个新的 root，将原root 作为新root 的左孩子
            return new TreeNode(val, root, nullptr);
        if(2 == depth){
        // 需要在root下新增两个节点，原来的左(右)子树是新的left(right)的左(右)子树。
            root->left = new TreeNode(val, root->left, nullptr);
            root->right = new TreeNode(val, nullptr, root->right);
        }else{
            // 递归向下找到depth为2的节点进行插入
            root->left = addOneRow(root->left, val, depth-1);
            root->right = addOneRow(root->right, val, depth-1);
        }
        return root;
    }
};